package leetcode;

import java.util.*;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2022-02-21 19:12
 **/
public class LeetCode838 {

    //bfs
    public String pushDominoes(String dominoes) {
        Deque<Integer> q = new ArrayDeque<>();
        int n = dominoes.length();
        List<Character>[] force = new List[n];
        //数组 time 记录骨牌翻倒或者确定不翻倒的时间
        int[] time = new int[n];
        Arrays.fill(time, -1);

        for (int i = 0; i < n; i++) {
            force[i] = new ArrayList<>();
        }

        for (int i = 0; i < n; i++) {
            char c = dominoes.charAt(i);
            if (c != '.') {
                q.offer(i);
                //记录初始时间就确定翻倒的牌
                time[i] = 0;
                //记录牌收到的力
                force[i].add(c);
            }
        }

        char[] res = new char[n];
        Arrays.fill(res, '.');

        while (!q.isEmpty()) {
            int i = q.poll();
            int t = time[i];
            //如果i号牌只受一个力,受两个力则说明不变
            if (force[i].size() == 1) {
                char c = force[i].get(0);
                res[i] = c;
                int ni = c == 'L' ? i - 1 : i + 1;
                if (ni >= 0 && ni < n) {
                    //如果ni号牌没受过力,修改其是否翻牌的确定时间
                    if (time[ni] == -1) {
                        time[ni] = t + 1;
                        force[ni].add(c);
                        q.offer(ni);
                    } else if (time[ni] == t + 1) {
                        //time[ni] = t + 1说明ni号牌已经受过一个力了,收受到了第二个力
                        force[ni].add(c);
                    }
                }

            }
       }

        return new String(res);
    }

}
